//===----------------------------------------------------------------------===//
//
//                         BusTub
//
// lru_k_replacer.cpp
//
// Identification: src/buffer/lru_k_replacer.cpp
//
// Copyright (c) 2015-2022, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include "buffer/lru_k_replacer.h"
#include<memory>

namespace bustub {

LRUKReplacer::LRUKReplacer(size_t num_frames, size_t k) : replacer_size_(num_frames), k_(k) {}

auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool { 
    auto iter = this->history.begin();
    for(;iter!=this->history.end();iter++){
        if(this->evictable.find(iter->first)!=this->evictable.end()&&this->evictable[iter->first])
            break;
    }
    if(iter!=this->history.end()){
        *frame_id = iter->first;
        this->history.erase(iter);
        this->evictable.erase(*frame_id);
        this->index.erase(*frame_id);
        this->evictable_size--;
        return true;
    }else{
        iter = this->buff.begin();
        for(;iter!=this->buff.end();iter++){
            if(this->evictable.find(iter->first)!=this->evictable.end()&&this->evictable[iter->first])
                break;
        }
        if(iter!=this->buff.end()){
            *frame_id = iter->first;
            this->buff.erase(iter);
            this->index.erase(*frame_id);
            this->evictable.erase(*frame_id);
            this->evictable_size--;
            return true;
        }
    }
    return false; 
}

void LRUKReplacer::RecordAccess(frame_id_t frame_id) {
    if(frame_id>int32_t(this->replacer_size_))
        return; // 报错，新增的页面大于最大值
    
    if(this->index.find(frame_id)==this->index.end()){
        this->history.push_back({frame_id,1});//
        this->index[frame_id]={frame_id,1};
        this->curr_size_++;
        this->evictable[frame_id]=false;
    }
    else{
        Node &node = this->index[frame_id];
        auto lists = &this->history;
        // std::list<Node> *list=&(this->history);
        if(node.second==this->k_){
            lists = &this->buff;
        }
        node.second++;

        if(node.second>this->k_){
            node.second=this->k_;
            auto iter = lists->begin();
            for(;iter!=lists->end();iter++){
                if(iter->first==frame_id)
                    break;
            }
            Node n_node = *iter;
            lists->erase(iter);
            lists->push_back(n_node);
            //LRU
        }else if(node.second==this->k_){
            //add to buff,del node in history
            auto iter = lists->begin();
            for(;iter!=lists->end();iter++){
                if(iter->first==frame_id)
                    break;
            }
            Node n_node = *iter;
            n_node.second=node.second;
            lists->erase(iter);
            this->buff.push_back(n_node);
        }else{
            //FIFO
            for(auto &e : *lists){
                if(e.first==frame_id){
                    e.second=node.second;
                }
            }
        } 
    }
}

void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
    if(this->evictable.find(frame_id)==this->evictable.end()){
        return ; // error frame_id
    }
    // bool temp = set_evictable==this->evictable[frame_id];
    // if(!temp){
    //     if(set_evictable)
    //             this->evictable_size++;
    //     else
    //             this->evictable_size--;
    //     this->evictable[frame_id]=set_evictable;
    // } 
    
    // bool temp = set_evictable==this->evictable[frame_id];
    // if(!temp){
    if(set_evictable)
        this->evictable_size++;
    else
        this->evictable_size--;
    this->evictable[frame_id]=set_evictable;
    // } 
}

void LRUKReplacer::Remove(frame_id_t frame_id) {
    if(this->evictable.find(frame_id)==this->evictable.end())
        return;
    
    if(this->evictable[frame_id]==false)
        return;
    
    auto iter = this->history.begin();
    for(;iter!=this->history.end();iter++){
        if(iter->first==frame_id)
            break;
    }
    if(iter!=this->history.end()){
        this->history.erase(iter);
        return ;
    }else{
        iter=this->buff.begin();
        for(;iter!=this->buff.end();iter++){
            if(iter->first==frame_id)
                break;
        }
        if(iter!=this->buff.end())
            this->buff.erase(iter);
    }
}

auto LRUKReplacer::Size() -> size_t {
    return this->evictable_size;
}

}  // namespace bustub
